On the Restricted Isometry of the Columnwise Khatri-Rao Product

摘要

The columnwise Khatri-Rao product of two matrices is an important matrixtype, reprising its role as a structured sensing matrix in many fundamentallinear inverse problems. Robust signal recovery in such inverse problems isoften contingent on proving the restricted isometry property (RIP) of a certainsystem matrix expressible as a Khatri-Rao product of two matrices. In thiswork, we analyze the RIP of a generic columnwise Khatri-Rao product by derivingtwo upper bounds for its $k$-th order Restricted Isometry Constant ($k$-RIC)for different values of $k$. The first RIC bound is computed in terms of theindividual RICs of the input matrices participating in the Khatri-Rao product.The second RIC bound is probabilistic in nature, and is specified in terms ofthe input matrix dimensions. We show that the Khatri-Rao product of a pair of$m \times n$ sized random matrices comprising independent and identicallydistributed subgaussian entries satisfies $k$-RIP with arbitrarily highprobability, provided $m$ exceeds $\mathcal{O}(\sqrt{k} \log^{3/2} n)$. This isa substantially milder condition compared to $\mathcal{O}(k \log n)$ rowsneeded to guarantee $k$-RIP of the input subgaussian random matricesparticipating in the Khatri-Rao product. Our results confirm that theKhatri-Rao product exhibits stronger restricted isometry compared to itsconstituent matrices for the same RIP order. The proposed RIC bounds arepotentially useful in obtaining improved performance guarantees in severalsparse signal recovery and tensor decomposition problems.